\section{高次同余式}

\begin{frame}{高次同余式}
  \begin{lemma}%引理1
    设 $f(x)=a_{n} x^{n}+\cdots+a_{1} x+a_{0}$ 为整数系数多项式， 
    $m=m_{1} m_{2} \cdots m_{t}$, 其中 $m_{1}, \cdots, m_t$ 两两互素。
    那么
\[
f(x) \equiv 0 \left(\mod m\right) \quad \Leftrightarrow \quad
\begin{cases}
  f(x) \equiv 0  \left(\mod m_{1}\right) \\
  \quad \vdots \\
  f(x) \equiv 0  \left(\mod m_{t}\right).
\end{cases}
\]
也就是说，整数 $x_{0}$ 满足 $f\left(x_{0}\right) \equiv 0\left(\mod m\right)$ 当且仅当
$f\left(x_{0}\right) \equiv 0 \left(\mod m_{i}\right)$ ($1 \leqslant i \leqslant t$);
且满足 $f\left(x_{0}\right) \equiv 0\left(\mod m\right)$ 的 $x_{0}$ 的模 $m$ 同余类个数 (解数) , 等于满足各 $f\left(x_{0}\right) \equiv$ $0\left(\mod m_{i}\right)$ 的 $x_{0}$ 模 $m_{i}$ 同余类个数 (解数) 之积 ($1 \leqslant i \leqslant t$).
\end{lemma}

\pause
\begin{proof}
等价性源自 $m \mid f\left(x_{0}\right)$ 当且仅当 $m_{i} \mid f\left(x_{0}\right)$ $(1 \leqslant i \leqslant t)$. 
解的个数的断言可通过限制孙子分解得到。
\pause
诚然，
任取 $f(x) \equiv 0\left(\mod m_{i}\right)$ 的解 $x \equiv b_i\left(\mod m_i\right)$ ($1\leqslant i\leqslant t$), 
可由孙子定理得 $f(x) \equiv 0\left(\mod m\right)$ 的唯一的 $x \equiv a\left(\mod m\right)$ 
使 $a \equiv b_i\left(\mod m_i\right)$ ($1\leqslant i\leqslant t$); 从而
 \[
   f(a) \equiv f\left(b_{i}\right) \equiv 0 \left(\mod m_{i}\right) \quad(1 \leqslant i \leqslant t),
 \]
 于是 $f(a) \equiv 0\left(\mod m\right)$. 
 \pause
 这样，$f(x) \equiv 0\left(\mod m_{i}\right)$ 的解 $x \equiv b_i\left( \mod m_i \right)$构成的$t$元对
 $(b_1,\cdots,b_t)$一一对应于
 $f(x)\equiv 0\left( \mod m \right)$的解$x\equiv a\left( \mod m \right)$.
\pause
 若 $b_{i}$ 有 $n_{i}$ 种取法 (即 $f(x) \equiv 0\left(\mod m_{i}\right)$ 有 $n_{i}$ 个解)，
 则 $\left(b_{1}, \cdots, b_{t}\right)$ 有 $n_{1} \cdots n_{t}$ 种取法，这也是解 $a$ 的个数。
 \end{proof}
 \end{frame}

 \begin{frame}

 设 $m=p_{1}^{s_{1}} p_{2}^{s_{2}} \cdots p_{t}^{s_{t}}$ 为素因子分解， 则由引理 1 知， 同余式 $f(x) \equiv 0\left(\mod m\right)$ 归结为 (模素数幂的同余式):
 \[
 f(x) \equiv 0 \left(\mod p_{i}^{s_{i}}\right) \quad(i=1, \cdots, t)
 \]

 ~

 \pause
 设 $(a, m)=1$, 若 $x^{n} \equiv a\left(\mod m\right)$ 有整数解 $x$, 则称 $a$ 为模 $m$ 的 $n$ 次剩余;
 否则称为 $n$ 次非剩余。 
 上述说明， 模 $m$ 的 $n$ 次剩余问题， 归结为模 $p_{i}^{s_{i}}$ 的 $n$ 次剩余问题。

 \pause

 ~

 上节对有原根 (包括模 $m=2, 4, p^{s}$, 其中 $p$ 为奇素数) 情形的 $n$ 次剩余问题已得结果：
 \[
   \begin{aligned}
   x^{n} \equiv a \left(\mod m\right) \text { 有解 } \quad & \Leftrightarrow \quad d=(n, \varphi(m)) \mid \text { ind } a \\
 & \Leftrightarrow \quad a^{\varphi(m) / d} \equiv 1 \left(\mod m\right),
 \end{aligned}
 \]
 且有解时解的个数为 $d$.

 ~

 \pause
 现在， 考虑模 $2^{s}$ 情形 ($s\geqslant 3$)。 由 §3.3 定理 1 知， $s \geqslant 3$ 时， 
 \[
   \left(\mathbb{Z} / 2^{s} \mathbb{Z}\right)^{*}=\{(-\overline{1})^{\delta} \overline{5}^{k}\},
 \]
 其中$\delta$ 和 $k$ 分别遍历模 $2$ 和模 $2^{s-2}$ 任一剩余系。
 \pause
 若 $a \equiv(-1)^{\delta} 5^{k}\left(\mod 2^{s}\right)$, 
 则称 $(\delta, k)$ 为 \emph{$a$ 对模 $2^{s}$ 的指标组}， 记为 $\operatorname{ind} a$. 
 也有性质： $\operatorname{ind} (a b)=\operatorname{ind} a+\operatorname{ind} b$.
 \end{frame}

 \begin{frame}
  \begin{theorem}%定理1
  考虑同余式 $x^{n} \equiv a\left(\mod 2^{s}\right)$ ($s \geqslant 3$, $a$ 为奇数)。记
\[
  d_{0}=(n, 2),\quad  d=\left(n, 2^{s-2}\right),\quad  a \equiv(-1)^{\delta} 5^{k},
\]
则
\[
  \begin{aligned}
  x^{n} \equiv a \left(\mod 2^{s}\right) \text { 有解 }\quad & \Leftrightarrow \quad
  \left(d_{0}, d\right) \mid \operatorname{ ind } a=(\delta,k)\quad \left(\text{即~} d_{0}\mid \delta, d\mid k\right) \\
  & \Leftrightarrow \quad a^{\frac{2}{d_{0}}} \equiv 1 \left(\mod 4\right) \text {~且~} a^{\frac{2^{s-2}}{d}} \equiv 1 \left(\mod 2^{s}\right) .
\end{aligned}
\]
而且有解时解的个数为 $d_{0} d$. (特别地， $n$ 为奇数时有唯一解。)
\end{theorem}

\pause
\begin{proof}
 设 $x \equiv(-1)^{\varepsilon} 5^{y}\left(\mod 2^{s}\right)$. 
 那么$x^{n} \equiv a\left(\mod 2^{s}\right)$ 化为
 \[
 (-\overline{1})^{n \varepsilon} \overline{5}^{n y} \equiv(-\overline{1})^{\delta} \overline{5}^{k} \quad\left(\mod 2^{s}\right)
 \]
 即
 \[
 n \varepsilon \equiv \delta \left(\mod 2\right), \quad n y \equiv k \left(\mod 2^{s-2}\right)
 \]
 \pause
 由 \S2.3 系 2 知， 上两式有解 $\varepsilon$ 和 $y$ 分别相当于
 $d_{0}\mid \delta,  d\mid  k$;
 且有解时解数分别为 $d_{0}$ 和 $d$, 故 $x$ 的解数为 $d_{0} d$.
 \pause
 因 $-1\left(\mod 4\right)$ 的阶为 $2$, 而 $5\left(\mod 2^{s}\right)$ 的阶为 $2^{s-2}$, 
 故$d_{0}\mid \delta,  d\mid  k$分别相当于
\[
  (-1)^{\frac{2\delta}{d_{0}}} \equiv 1 \quad\left(\mod 4\right), \quad 5^{\frac{2^{s-2} k}{ d}} \equiv 1 \quad\left(\mod 2^{s}\right).
 \]
  \end{proof}
 \end{frame}

 \begin{frame}
   \begin{proof}[续]
  注意到 $a \equiv(-1)^{\delta} 5^{k} \equiv(-1)^{\delta}\left(\mod 4\right)$, 
  故$(-1)^{\frac{2\delta}{d_{0}}} \equiv 1 \left(\mod 4\right)$相当于
  $a^{\frac{2}{d_{0}}} \equiv 1 \left(\mod 4\right)$.
  \pause
又注意到 $n$ 为偶数时 $d_{0}=2$, $\delta$ 为偶数; $n$ 为奇数时 $d=1$; 
故总有 $(-1)^{\delta \frac{2^{s-2}}{ d}} \equiv 1\left(\mod 2^{s}\right)$. 
而$a \equiv(-1)^{\delta} 5^{k}\equiv \left(\mod 2^{s}\right)$,
  故$5^{\frac{2^{s-2} k}{ d}} \equiv 1 \left(\mod 2^{s}\right)$相当于
    $a^{\frac{2^{s-2}}{ d}} \equiv 1 \left(\mod 2^{s}\right).$
    证毕。
   \end{proof}
   \pause

   \begin{example}
     我们应用定理1证明中的方法解$x^4\equiv 17\left( \mod 2^5 \right)$. 
\pause
     此时
     \[
       a=17, s=5, n=4, \quad d_0=(n,2)=2, \quad d=(n,2^{s-2})=4.
     \]
     \pause
     由于$a=17\equiv 1\left( \mod 4 \right)$, $\delta=0$;
     由于$a=17\equiv 5^4\left( \mod 2^5 \right)$, $k=2$; 
     因此$\ind a=(0,4)$.
\pause
     $(d_0, d)\mid \ind a$表明该方程有解，且有$d_0d=8$个解。
     \pause
  令$x\equiv(-1)^{\varepsilon} 5^{y}\left(\mod 2^{s}\right)$. 
  $x$为解相当于其指标$(\varepsilon, y)$满足
  \[
    n \varepsilon \equiv \delta \left(\mod 2\right), \quad
    n y \equiv k \left(\mod 2^{s-2}\right),
  \]
  即
  \[
    4\varepsilon\equiv 0\left( \mod 2 \right), \quad 4y\equiv 4\left( \mod 2^3 \right).
  \]
  \pause
  解得$\varepsilon\equiv 0, 1\left( \mod 2 \right)$, $y\equiv 1, 3, 5, 7\left( \mod 8 \right)$.
  \pause
  因此$x^4\equiv 17\left( \mod 2^5 \right)$有$8$个解为
  \[
    \begin{aligned}
      (-1)^0 5^1&\equiv 5,&  (-1)^0 5^3&\equiv 29, & (-1)^0 5^5&\equiv 21,& (-1)^0 5^7&\equiv 13,\\
      (-1)^1 5^1&\equiv 27,&  (-1)^1 5^3&\equiv 3, & (-1)^1 5^5&\equiv 11,& (-1)^1 5^7&\equiv 19.
    \end{aligned}
  \]
   \end{example}
 \end{frame}

 \begin{frame}{解的提升与Hensel引理}
   给定整系数多项式$f(x)$, 
   显然$f(x)\equiv 0\left( \mod p^{s+1} \right)$的整数解为$f(x)\equiv 0\left( \mod p^{s} \right)$的整数解。
   反过来呢？下面来看看如何提升$f(x)\equiv 0\left( \mod p^{s} \right)$的整数解为$f(x)\equiv 0\left( \mod p^{s+1} \right)$的整数解。
\pause
   \begin{theorem}%定理2
     设奇素数 $p$ 与 $a$ 及 $n$ 互素。 若 $x^{n} \equiv a\left(\mod p\right)$ 有解， 则 $x^{n} \equiv$ $a\left(\mod p^{s}\right)$ 有解 (对所有 $s \geqslant 1$); 反之也显然成立。 且它们的解数相同。
   \end{theorem}
\pause
   \begin{proof}
     只需对 $n \geqslant 2$ 证明。 对 $s$ 归纳。 设 $x^{n} \equiv a\left(\mod p^{s}\right)$ 有解 $x_{0}$, 希望 $x_{1}=$ $x_{0}+c p^{s}$ (其中$c$待定) 为模 $p^{s+1}$ 的解 (注意到$x_1\equiv x_0\left( \mod p^s \right)$)， 即满足
  \[
    a \equiv x_{1}^{n} \equiv x_{0}^{n}+n x_{0}^{n-1} c p^{s} \left(\mod p^{s+1}\right),\quad 
\pause
    \text{亦即~} a-x_0^n \equiv n x_{0}^{n-1} c p^{s} \left(\mod p^{s+1}\right).
\]
消去公因子$p^s$知
这相当于 
\(
  \left(a-x_{0}^{n}\right) / p^{s} \equiv n x_{0}^{n-1} c\left(\mod p\right).
\)
\pause
因 $p \nmid (n x_{0}^{n-1})$,
满足此条件的 $c$ 惟一地存在，如此得模 $p^{s+1}$ 解 $x_{1}$. 
\pause
而由上节定理 1 知， 
$x^{n} \equiv a\left(\mod p^{s+1}\right)$ 的解数为
\[
  \left(n, \varphi\left(p^{s+1}\right)\right)=\left(n, p^{s}(p-1)\right)=(n, p-1),
\]
此与 $x^{n} \equiv a\left(\mod p\right)$ 解数相同。
\end{proof}
\end{frame}

\begin{frame}
 \begin{theorem}%定理3
   若 $x^{n} \equiv a\left(\mod 2^{2 v+1}\right)$ 有解 (其中 $a$ 为奇数，$v=v_2(n)$为$n$的$2$-进赋值), 则
 \[
   x^{n} \equiv a \left(\mod 2^{s}\right)
 \]
 对所有 $s \geqslant 2 v+1$ 有解， 反之亦然；
 且解数都相同 (而且对 $s \geqslant 1$ 也有解 (但解数不同))。
 \end{theorem}
\pause
 \begin{proof}
   由定理 1 知$n$为奇数时 (此时$v=0$) $x^n\equiv a\left( \mod 2^s \right)$ 解存在且惟一，对任意$s\geqslant 1$, 故断言成立。 
   下面假设$n$为偶数，故$v\geqslant 1$.
   \pause
   对 $s\geqslant 2 v+1$ 归纳。
   设 $x^{n} \equiv a\left(\mod 2^{s}\right)$ 有解$x_{0}$, 此必为奇数。 
   \pause
   记 $n=2^{v} n_{1}$, $n_{1}$ 为奇数。 令 $x_{1}=x_{0}+c 2^{s-v}$, 欲待定 $c$ 使其为模 $2^{s+1}$ 的解， 即
\[
  a \equiv x_{1}^{n} \equiv x_{0}^{n}+n x_{0}^{n-1} c 2^{s-v} \left(\mod 2^{s+1}\right),
  \pause
  \quad \text{亦即~} 
  a- x_0^n \equiv n_1 x_{0}^{n-1} c 2^{s} \left(\mod 2^{s+1}\right).
\]
\pause
消去公因子$2^s$知
这相当于 $\left(x_{0}^{n}-a\right) / 2^{s} \equiv n_{1} x_{0}^{n-1} c \equiv c\left(\mod 2\right)$. 
用此种 $c$ 即可得 $x_{1}$ 使 $x_{1}^{n} \equiv a \left(\mod 2^{s+1}\right)$. 
由数学归纳法， 定理前半部分得证。 
\pause
而由定理 1 知， 解数为
\[
d_{0} d=(n, 2)\left(n, 2^{s-2}\right)=2^{v+1}
\]
与 $s$ 无关 ($s \geqslant 2 v+1$且$v\geqslant 1$时 $s-2 \geqslant v$). 
\pause
最后， $x_{0}^{n} \equiv a\left(\mod 2^{2 v+1}\right)$ 蕴含
\[
  x_{0}^{n} \equiv a \left(\mod 2^{k}\right) \quad(k=1, \cdots, 2 v).
\]
\end{proof}
\end{frame}

\begin{frame}

  注意$n$为偶数时等价类$c\left( \mod 2 \right)$中整数会给出$2^v$个不同的(模$2^{s+1}$)的解。

  \pause
  \begin{example}%例1
  $n=2$ 时， $v=1,2 v+1=3$. $x^{2} \equiv 1\left(\mod 2^{3}\right)$ 有解 $x_{0}=1,3,5,7$. 
\pause
  可推知
\[
x^{2} \equiv 1 \quad\left(\mod 2^{4}\right)
\]
也有 $4$ 解， 实求之为 $1,7,9,15$.
模 $2^{5}$ 也有 $4$ 解： $1,15,17,31$. 
\pause
但模 $4$ 只有两解： $1,3$. 模 $2$ 只有一解。 
\pause
另一方面， $x^{2} \equiv 5\left(\mod 2^{3}\right)$ 无解， 故 $x^{2} \equiv 5\left(\mod 2^{4}\right)$必无解， 而 $x^{2} \equiv 5\left(\mod 2^{2}\right)$ 有解。

~

\pause
例如，要求得$x^{2} \equiv 1 \left(\mod 2^{4}\right)$的解，我们可以对$U_{16}$中元素逐个检验，
可以应用定理1证明中方法，也可以应用定理3证明中方法提升$x_0$.
我们展示下如何提升$x^{2} \equiv 1\left(\mod 2^{3}\right)$的解$x_0=1,3,5,7$
得到$x^{2} \equiv 1 \left(\mod 2^{4}\right)$的解。
\pause
用定理3的记号: $n=2, v=1, s=3, s-v=2$. 若
$x_1=x_0+c\cdot 2^{s-v}=x_0+4c$
为提升的解，则
\[
\begin{gathered}
  0\equiv x_1^2-1=(x_0+4c)^2-1=x_0^2-1+8x_0c \left( \mod 2^4 \right),\\
  0= \frac{x_0^2-1}{8} + c\left( \mod 2 \right), \quad c\equiv \frac{x_0^2-1}{8}\left( \mod 2 \right).
\end{gathered}
\]
\pause
提升$x_0=1$. $c\equiv 0\left( \mod 2 \right)$. 取$c=0$得解$x_1=1$; 取$c=2$得解$x_1=9$. 
\pause
提升$x_0=3$. $c\equiv 1\left( \mod 2 \right)$. 取$c=1$得解$x_1=7$; 取$c=3$得解$x_1=15$.
\pause
这样我们已经得到$4$个解了，所以所有解为$1,7,9,15$
($x_0=5, 7$提升得到的解必定也是这些)。
\end{example}
\end{frame}

\begin{frame}

\begin{example}%例2
  \label{提升x^2-2(mod 7)的解}
考虑方程
$x^{2}-2=0$.
它显然没有整数解。 
转而考虑其模 $p$ 的解。 
比如取 $p=7$来考虑。
\pause
$x^{2}-2=0\left(\mod 7\right)$
有解 $x_{0}= 3$. 即 $x=x_{0}+c_{1} p$ 均为其解 $\left(c_{1} \in \mathbb{Z}\right)$. 
\pause
再考虑 
$x^{2}-2=0\left(\mod 7^{2}\right)$
的解， 以 $x=x_{0}+c_{1} p$代入得
\[
0 \equiv x^{2}-2 \equiv x_{0}^{2}-2+2 x_{0} c_{1} p \equiv 7+6 c_{1} 7 \quad\left(\mod 7^{2}\right)
\]
化为 
  $0 \equiv 1-c_{1}\left(\mod 7\right),$
故得解 
\(
  x_{1}=3+7.
\)
\pause
如此类似可得模 $7^{3}$ 的解 
\(
  x_{2}=3+7+2 \cdot 7^{2},
\)
模 $7^{4}$ 的解 
\(
  x_{3}=3+7+2 \cdot 7^{2}+6 \cdot 7^{3},
\)
等等。 
\pause
对任意 $0 < s \in \mathbb{Z}$, 可得 $x^{2}-2 \equiv$ $0\left(\mod p^{s}\right)$ 的解
\[
  x_{s-1}= x_{s-2}+a_{s-1} p^{s-1} 
    =a_{0}+a_{1} p+\cdots+a_{s-1} p^{s-1} \quad\left(0 \leqslant a_{i}<p\right)
\]
\end{example}

\pause
更一般地， 我们有
\begin{theorem}%定理4
  [Hensel (亨泽尔) 引理]
  设 $p$ 为素数， $f(x)$ 为整数系数多项式。
  若存在整数 $x_{0}$ (可设$0\leqslant x_0<p$) 使 $f\left(x_{0}\right) \equiv 0\left(\mod p\right)$ 而 
  $f^{\prime}\left(x_{0}\right) \nequiv 0\left(\mod p\right)$ 
  (其中$f^{\prime}$ 是 $f$ 的微商), 则对任意 $s \geqslant 1$,
  存在唯一的满足
  $x_{s-1} \equiv x_{s-2}\left(\mod p^{s-1}\right)$的整数$0\leqslant x_{s-1}< p^s$ 
  为同余式
  \[
    f(x) \equiv 0 \left(\mod p^{s}\right)
  \]
  的解 (解$x_{s-1}$ 称为 $x_{0}$ 的\emph{提升})。
  实际上，存在唯一的整数$a_0, a_1, \cdots$ 
  ($0 \leqslant a_{i}<p$)使得对任意 $s \geqslant 1$,
  \[
    x_{s-1}=a_{0}+a_{1} p+\cdots+a_{s-1} p^{s-1}.
  \]
\end{theorem}
\end{frame}

\begin{frame}


\begin{proof}
  对$s\geqslant 1$归纳。 $s=1$ 时 $a_{0}=x_0$.
\pause
假设定理对 $s$ 成立， 希望 $x_{s}=x_{s-1}+a_s p^{s}$ (待定 $a_s$) 满足 $f\left(x_{s}\right) \equiv 0\left(\mod p^{s+1}\right)$, 即
 \[
 0 \equiv f\left(x_{s}\right)=f\left(x_{s-1}+a_s p^{s}\right)=f\left(x_{s-1}\right)+f^{\prime}\left(x_{s-1}\right) a_s p^{s} \quad\left(\mod p^{s+1}\right)
 \]
 (用到了多项式的 Taylor 展开，见引理~\ref{Taylor展开}). 
\pause
因$p^s\mid f(x_{s-1})$, 这相当于
\[
\begin{aligned}
  0 \equiv f(x_{s-1})/p^s+f'(x_{s-1})a_s & \left( \mod p \right),\quad \text{亦即~} \\
  -f(x_{s-1})/p^s \equiv f'(x_{s-1})a_s &  \left( \mod p \right).
\end{aligned}
\]
因 $f^{\prime}\left(x_{s-1}\right)\equiv f'(x_0) \nequiv 0\left(\mod p\right)$, 
这样的$a_s$惟一地存在，即 
\[
  a_s \equiv- (f\left(x_{s-1}\right)/p^{s}) f^{\prime}\left(x_{s-1}\right)^{-1} \left(\mod p\right).
\]
 \end{proof}

\pause
 \begin{lemma}[多项式的Taylor展开]
   设$f=\sum_{k=0}^n c_k x^k \in \RR[x]$. 那么对任意的$a\in \RR$,
\[
  f(x)=\sum_{k=0}^n \frac{f^{(k)}(a)}{k!}(x-a)^k,
\]
而且系数 $\frac{f^{(k)}(a)}{k!}$ 是 $a$的整系数的多项式。
   \label{Taylor展开}
 \end{lemma}
\end{frame}



 \begin{frame}

 \begin{proof}
  $f(x)=\sum_{k=0}^n \frac{f^{(k)}(a)}{k!}(x-a)^k$是我们熟知的。
只用说明$\frac{f^{(k)}(a)}{k!}$为$a$的整系数的多项式。
易知只用对$f(x)=x^n$说明。此时
\[
  x^n=(x-a+a)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}(x-a)^k,
\]
系数$\binom{n}{k}a^{n-k}$确实为$a$的整系数的多项式。
 \end{proof}
 
 \pause
 此方法中，由Hensel引理的证明中$a_s$的公式知 
   \[
     x_{s}=x_{s-1}+a_s p^{s} \equiv x_{s-1}-f\left(x_{s-1}\right) / f^{\prime}\left(x_{s-1}\right),
   \]
   其中$1/f'(x_{s-1})$是$f'(x_{s-1})\left( \mod p \right)$的逆。 
   这与微积分中的 Newton (牛顿)求根法 (Newton's method)很类似。 Newton 法从一点 $x_{0}$ (实数)开始， 用迭代极限法求出方程 $f(x)=0$ 的实根： $x_{s}=x_{s-1}-f\left(x_{s-1}\right) / f^{\prime}\left(x_{s-1}\right)$.

 \pause

 \begin{center}
   % 取自 https://tex.stackexchange.com/questions/551160/plot-that-demonstrate-newtons-method
   % 这里有画切线的方法：https://tex.stackexchange.com/questions/25928/how-to-draw-tangent-line-of-an-arbitrary-point-on-a-path-in-tikz
\begin{tikzpicture}[thick,scale=0.25]

% Axes
\draw[->,name path=xaxis] (-1,0) -- (15,0) node[above]{$x$};
\draw[->] (0,-2) -- (0,8)node[right]{$y$};;

% Function plot
\draw[ultra thick, orange,name path=function]  plot[smooth,domain=1:9.5] (\x, {0.1*\x^2-1.5}) node[left]{$f(x)$};

% plot tangent line
\node[violet,right=0.2cm] at (8,4.9) {切线$y-f(x_s)=f'(x_s)(x-x_s)$};

\draw[gray,thin,dotted] (8,0) -- (8,4.9) node[circle,fill,inner sep=2pt]{};
\draw[dashed, violet,name path=Tfunction]  plot[smooth,domain=4.25:9.5] (\x, {1.6*\x-7.9});

% x-axis labels
\draw (8,0.1) -- (8,-0.1) node[below] {$x_{s}$};
\draw [name intersections={of=Tfunction and xaxis}] ($(intersection-1)+(0,0.1)$) -- ++(0,-0.2) node[below,fill=white] {$x_{s+1}$} ;
\end{tikzpicture}
 \end{center}
\end{frame}

 \begin{frame}
   \begin{example}
     我们用公式
  \[
    x_{s}\equiv x_{s-1} - f(x_{s-1})/f'(x_{s-1}) \left( \mod p^{s+1} \right)
\]
  来算出例~\ref{提升x^2-2(mod 7)的解}~中提升$x_0=3$得到的模$7^2,7^3,7^4$的解$x_1, x_2, x_3$.
  我们有$p=7$, $f=x^2-2$, $f'=2x$. 
  从而
  \[
f'(x_0)=6 \left( \mod 7 \right), \quad
  f'(x_{0})^{-1} \equiv -1\left( \mod 7 \right).
  \]
\pause
  由于提升得到的$x^2-2\equiv 0\left( \mod p^s \right)$的解$x_{s-1}$
满足$x_{s-1}\equiv x_0\left( \mod 7 \right)$, 有
\[
  f'(x_{s-1})^{-1} \equiv f'(x_0)^{-1}\left( \mod 7 \right).
\]
\pause
进而有
\[
  \begin{aligned}
    x_{1} &\equiv  x_0-f(x_0)/f'(x_0)\equiv x_0+7=3+7\left( \mod 7^2 \right),\\
    \pause
x_{2} &\equiv  x_1-f(x_1)/f'(x_1)\equiv x_1-f(x_1)/f'(x_0)\\
& \equiv x_1+98=3+7+2\cdot 7^2\left( \mod 7^2 \right),\\
\pause
x_{3} &\equiv  x_2-f(x_2)/f'(x_2)\equiv  x_2-f(x_2)/f'(x_0) \\
& \equiv x_2+11662\equiv x_2+2058= 3+7+2\cdot 7^2+6\cdot 7^3\left( \mod 7^4 \right),\\
  \end{aligned}
\]
   \end{example}
 \end{frame}


 \begin{frame}

   \begin{example}
     求解$x^3+x^2+29\equiv 0\left( \mod 25 \right)$. 
\pause
     令$f(x)=x^3+x^2+29$.
     试探可得$f(x)\equiv 0\left( \mod 5 \right)$有唯一解$x\equiv 3\left( \mod 5 \right)$.
     \pause
     我们有$f'(3)\equiv 3\nequiv 0\left( \mod 5 \right)$, 且$f'(3)^{-1}\equiv 2\left( \mod 5 \right)$.
     可应用Hensel引理提升$f(x)$模$5$的解$3$,
提升的解为
\(
  x\equiv 3-f(3)/f'(3) \equiv 23\left( \mod 25 \right).
\)
\pause
因此$f(x)\equiv 0\left( \mod 25 \right)$的唯一解为$x\equiv 23\left( \mod 25 \right)$.
   \end{example}

   \pause
 \begin{comment*}%评述
 定理 2 和定理 3 实为定理 4 的应用。 定理 4 (和例 2) 开创了一种无限制的过程， 即对任意自然数 $s$, 可求得 $f(x) \equiv 0$ 模 $p^{s}$ 的解 $x_{s-1}=a_{0}+a_{1} p+\cdots+$ $a_{s-1} p^{s-1}\left(0 \leqslant a_{i}<p\right)$. 这实际上就得到了无限级数
 \[
 x=a_{0}+a_{1} p+\cdots+a_{s-1} p^{s-1}+\cdots
 \]
 这种 “无限级数”称为 $p$-adic 数 ($p$ 进数)（它不需要普通微积分意义下的收敛，而另创收敛理论). 随着 $s$ 的不断增大， 此级数在某种意义上是收敛的， $p^{s}$ 似乎是微不足道的。 这种观念开辟了一种新的 “数值大小观”和新的 “序列收敛观” （赋值论和完备化）, 创立了无限多个与实数域 $\mathbb{R}$ 平行的完备域(即 Cauchy(柯西) 序列收敛的域) $Q_{p}$ (从而将实数域记为 $\mathbb{R}=Q_{\infty}$), 成为了现代许多数学学科的基础、语言、工具和方法 (详见附录 4). 当然， $p$-adic 数的基础还是模算术，虽是无穷， 但往往归结到模 $p$ 或模 $p^{2}$ 等。 这种观念带来反极限的概念。 论数者赞这“ $p$-adic 数之奇” :
 \begin{poem}
 模之又模幂次多， 模成无限偏蒂克( $p$-adic).\\
 莫道级数通无限， 无限常归有限做。
 \end{poem}
 \end{comment*}\end{frame}


\begin{frame}{小结}
  \begin{enumerate}
    \item 给定整系数多项式$f(x)$, 解释如何$f(x)\equiv 0\left( \mod m \right)$的求解问题可以归结
      为$f(x)\equiv 0\left( \mod p^{s} \right)$的求解问题。解数如何关联？
    \item 令$s\geqslant 3$. 奇数模$2^s$的指标 (组) 指什么？
    \item 模$2^s$ ($s\geqslant 3$) 的$n$次剩余问题如何判断解的存在性？如何求解？
      解数如何？
    \item 如何提升$x^n\equiv a\left( \mod p \right)$ (其中$p\nmid a, p\nmid n$) 的解得到
      $x^n\equiv a\left( \mod p^s \right)$的解？关于解数有何结论？
    \item 如何提升$x^n\equiv a\left( \mod 2^{2v+1} \right)$ (其中$2\nmid a$, $v=v_2(n)$) 的解得到
      $x^n\equiv a\left( \mod 2^s \right)$的解 ($s\geqslant 2v+1$)？
      关于解数有何结论？
      \item 描述Hensel引理。
  \end{enumerate}
\end{frame}
